#include <bits/stdc++.h>

using namespace std;

// 统计整数数目
// 给你两个数字字符串 num1 和 num2 ，以及两个整数max_sum和min_sum
// 如果一个整数 x 满足以下条件，我们称它是一个好整数
// num1 <= x <= num2
// min_sum <= digit_sum(x) <= max_sum
// 请你返回好整数的数目
// 答案可能很大请返回答案对10^9 + 7 取余后的结果
// 注意，digit_sum(x)表示x各位数字之和
// 测试链接 : https://leetcode.cn/problems/count-of-integers/

class Solution 
{
public:
    static const int MOD = 1000000007;
    static const int MAXN = 23;
    static const int MAXM = 401;
    int dp[MAXN][MAXM][2];
    string num;
    int mn, mx, len;

    void build()
    {
        for(int i = 0; i < len; ++i)
        {
            for(int j = 0; j <= mx; ++j)
            {
                dp[i][j][0] = -1;
                dp[i][j][1] = -1;
            }
        }
    }

    int count(string num1, string num2, int min_sum, int max_sum) 
    {
        mn = min_sum;
        mx = max_sum;
        num = num2;
        len = num2.size();
        build();
        int ans = f(0, 0, 0);
        num = num1;
        len = num1.size();
        build();
        ans = (ans - f(0, 0, 0) + MOD) % MOD;
        if(check()) ans = (ans + 1) % MOD;
        return ans;
    }

	// 注意：
	// 数字，char[] num
	// 数字长度，int len
	// 累加和最小要求，int min
	// 累加和最大要求，int max
	// 这四个变量都是全局静态变量，所以不用带参数，直接访问即可
	// 递归含义：
	// 从num的高位出发，当前来到i位上
	// 之前决定的数字累加和是sum
	// 之前的决定已经比num小，后续可以自由选择数字，那么free == 1
	// 之前的决定和num一样，后续不可以自由选择数字，那么free == 0
	// 返回有多少种可能性
    int f(int i, int sum, int free)
    {
        // 超出最大和 max_sum 的限制
        if(sum > mx) return 0;
        // 后序的数无论如何选，都无法满足 >= min_sum 的条件
        if(sum + (len - i) * 9 < mn) return 0;
        // 找到符合条件的一个数了
        if(i == len) return 1;
        // 缓存命中
        if(dp[i][sum][free] != -1) return dp[i][sum][free];
        // cur : num当前位的数字
        int cur = num[i] - '0';
        int ans = 0;
        if(free == 0)
        {
            // 还不能自由选择
            for(int pick = 0; pick < cur; ++pick)
            {
                ans = (ans + f(i + 1, sum + pick, 1)) % MOD;
            }
            ans = (ans + f(i + 1, sum + cur, 0)) % MOD;
        }
        else
        {
            // 可以自由选择
            for(int pick = 0; pick <= 9; ++pick)
            {
                ans = (ans + f(i + 1, sum + pick, 1)) % MOD;
            }
        }
        dp[i][sum][free] = ans;
        return ans;
    }

    bool check()
    {
        int sum = 0;
        for(char ch : num) sum += ch - '0';
        return mn <= sum && sum <= mx;
    }
};


class Solution 
{
private:
    const int MOD = 1000000007;
    
    // 如果一个整数 x 满足以下条件，我们称它是一个好整数
    // 返回 [1, s] 范围内的好整数的数目
    // 在本题中不需要考虑前导零问题
    int f(string& s, int min_sum, int max_sum)
    {
        int m = s.size(), dp[m][min(9 * m, max_sum) + 1];
        memset(dp, -1, sizeof dp); // -1 表示没有计算过
        function<int(int, int, bool)> f = [&](int i, int sum, bool is_limit) -> int
        {
            // 超出 max_sum 限制，直接返回 0
            if(sum > max_sum) return 0;
            // 后序的数无论如何选，都无法满足 >= min_sum 的条件
            if(sum + (m - i) * 9 < min_sum) return 0;
            // 每个位置都填上了数字，看看是否符合 >= min_sum 的条件
            if(i == m) return sum >= min_sum;
            // 缓存命中
            if(!is_limit && dp[i][sum] != -1) return dp[i][sum];
            int ret = 0;
            // 如果前面填的数字都和 n 的一样，那么这一位至多填数字 s[i]（否则就超过 n 啦）   
            int up = is_limit ? s[i] - '0' : 9;
            for(int d = 0; d <= up; ++d) // 枚举要填入的数字 d
            {
                ret = (ret + f(i + 1, sum + d, is_limit && d == up)) % MOD;
            }
            if(!is_limit) dp[i][sum] = ret;
            return ret;
        };
        return f(0, 0, true);
    }

public:
    int count(string num1, string num2, int min_sum, int max_sum) 
    {
        int ans = f(num2, min_sum, max_sum) - f(num1, min_sum, max_sum) + MOD;
        int sum = 0;
        for(char ch : num1) sum += ch - '0';
        ans += min_sum <= sum && sum <= max_sum; // x=num1 是合法的，补回来
        return ans % MOD;
    }
};